home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graphics / delaunay.c < prev    next >
C/C++ Source or Header  |  1994-08-05  |  6KB  |  362 lines
  1. #include <LEDA/impl/delaunay_tree.h>
  2. #include <LEDA/plane.h>
  3. #include <LEDA/window.h>
  4.  
  5.  
  6. window* Wp;
  7.  
  8. const double R = 1000;  // "length of inifinite rays"
  9.  
  10. int ymax;
  11.  
  12. int segment_to_points(segment s, list<point>& out, double dist)
  13. { 
  14.   int n = int(s.length()/dist) + 2;
  15.  
  16.   double dx = (s.xcoord2() - s.xcoord1())/n;
  17.   double dy = (s.ycoord2() - s.ycoord1())/n;
  18.   double x  = s.xcoord1();
  19.   double y  = s.ycoord1();
  20.  
  21.   out.append(s.start());
  22.  
  23.   for(int i = 0; i<n; i++)
  24.   { x += dx + double(random(-100,100))/1000000;
  25.     y += dy + double(random(-100,100))/1000000;
  26.     out.append(point(x,y));
  27.    }
  28.  
  29.   return n;
  30.  
  31. }
  32.  
  33. int circle_to_points(circle C, list<point>& out, double dist)
  34. { 
  35.   point c = C.center();
  36.   double r = C.radius();
  37.   int n = int(6.283 * r/dist);
  38.  
  39.   double alpha = 0;
  40.   double d = 6.283/n;
  41.  
  42.   for(int i = 0; i<n; i++)
  43.   { out.append(c.translate(alpha,r+double(random(-100,100))/1000000));
  44.     alpha += d;
  45.    }
  46.  
  47.   out.permute();
  48.  
  49.  return n;
  50.  
  51. }
  52.  
  53.  
  54.  
  55.  
  56. void draw_vor_site(double x, double y)
  57. { Wp->draw_point(x,y,blue); }
  58.  
  59. void draw_vor_seg(double x1, double y1, double x2, double y2,double,double)
  60. { Wp->draw_segment(x1,y1,x2,y2,red); }
  61.  
  62.  
  63. void draw_triang_seg(double x1, double y1, double x2, double y2)
  64. { Wp->draw_segment(x1,y1,x2,y2,green); 
  65.  }
  66.  
  67. void infi_pt(double x1, double y1, double x2, double y2, double *x, double* y)
  68. /* retourne le point a l'infini dans la direction x2 y2 depuis x1 y1*/
  69. {
  70.   vector v(x2,y2);
  71.  
  72.   v = v.norm();
  73.  
  74.   *x = x1 + R * v[0];
  75.   *y = y1 + R * v[1];
  76.   
  77. }
  78.  
  79.  
  80.  
  81. DELAUNAY_TREE<int> DT;
  82.  
  83. int display = 0;
  84. DT_item near_it = nil;
  85. bool vor = false;
  86. bool triang = false;
  87. list<segment> CH;
  88.  
  89.  
  90. void insert_point(point p)
  91. { Wp->draw_point(p,blue);
  92.   DT.insert(p,0);
  93.  }
  94.  
  95. void insert_segment(segment s)
  96. { list<point> pl;
  97.   segment_to_points(s,pl,10/Wp->scale());
  98.   point p;
  99.   forall(p,pl) insert_point(p);
  100. }
  101.  
  102. void insert_circle(circle c)
  103. { list<point> pl;
  104.   circle_to_points(c,pl,10/Wp->scale());
  105.   point p;
  106.   forall(p,pl) insert_point(p);
  107. }
  108.             
  109.  
  110.  
  111. void draw()
  112. { segment s;
  113.   switch(display) {
  114.  
  115.   case 0: DT.trace_voronoi_edges(draw_vor_seg,infi_pt);
  116.           break;
  117.  
  118.   case 1: DT.trace_triang_edges(draw_triang_seg);
  119.           break;
  120.  
  121.   case 2: { list<DT_item> L;
  122.             DT.convex_hull(L);
  123.             list_item it;
  124.             Wp->set_line_width(2);
  125.             forall_items(it,L) 
  126.             { point p = DT.key(L[it]);
  127.               point q = DT.key(L[L.cyclic_succ(it)]);
  128.               Wp->draw_segment(p,q,violet);
  129.              }
  130.             Wp->set_line_width(1);
  131.             break;
  132.            }
  133.   }
  134. }
  135.  
  136.  
  137. void redraw()
  138. { DT.trace_voronoi_sites(draw_vor_site);
  139.   draw();
  140. }
  141.  
  142.  
  143. void interactive(window& W)
  144. {
  145.   W.set_redraw(redraw);
  146.   W.set_mode(xor_mode);
  147.   W.set_node_width(4);
  148.  
  149.   panel P("DYNAMIC VORONOI DIAGRAMS");
  150.  
  151.   P.text_item("            based on Delaunay Trees           ");
  152.   P.text_item("             by Olivier Devillers             ");
  153.   P.text_item("                                              ");
  154.  
  155.   int but = -1;
  156.  
  157.   int N = 500;
  158.   int grid_width = 0;
  159.  
  160.   P.choice_item("show",display,"voronoi","triang","c-hull");
  161.   P.int_item("grid", grid_width,0,40);
  162.   P.int_item("rand sites ",N);
  163.  
  164.   P.button("random");
  165.   P.button("point");
  166.   P.button("segment");
  167.   P.button("circle");
  168.   P.button("delete");
  169.   P.button("neighbor");
  170.   P.button("clear");
  171.   P.button("quit");
  172.  
  173. for(;;)
  174. {
  175.   draw();  // draw picture
  176.  
  177.   but=P.open(0,0);
  178.  
  179.   if (but == 7) break;
  180.  
  181.   draw();  // delete previous drawing
  182.  
  183.   W.set_grid_mode(grid_width);
  184.  
  185.   switch (but) { 
  186.  
  187.     case 0: { for(int i=0; i<N; i++)
  188.                 insert_point(point(random(10,500),random(10,ymax)));
  189.               break;
  190.              }
  191.  
  192.     case 1: { point p;
  193.               while (W >> p)  insert_point(p);
  194.               break;
  195.              }
  196.  
  197.     case 2: { segment s;
  198.               while (W >> s) insert_segment(s);
  199.               break;
  200.              }
  201.  
  202.     case 3: { circle c;
  203.               while (W >> c) insert_circle(c);
  204.               break;
  205.              }
  206.  
  207.     case 4: { point p;
  208.               while (W >> p)
  209.               { DT_item it = DT.neighbor(p); 
  210.                 if (it) 
  211.                 { W.draw_point(DT.key(it),blue);
  212.                   DT.del_item(it); 
  213.                  }
  214.                }
  215.               break;
  216.              }
  217.  
  218.     case 5: { point p;
  219.               while (W >> p)
  220.               { if (near_it) W.draw_filled_node(DT.key(near_it));
  221.                 near_it = DT.neighbor(p); 
  222.                 if (near_it) W.draw_filled_node(DT.key(near_it));
  223.               }
  224.               if (near_it) W.draw_filled_node(DT.key(near_it));
  225.               near_it = nil;
  226.               break;
  227.              }
  228.  
  229.     case 6: { DT.clear();
  230.               W.clear();
  231.               CH.clear();
  232.               near_it = nil;
  233.              }
  234.     }  // switch
  235.  
  236.  } // for(;;)
  237.  
  238. }
  239.  
  240.  
  241.  
  242. void demo(int N, int sec)
  243. { int i;
  244.  
  245.   while(Wp->get_button() == 0)
  246.   {
  247.     DT.clear();
  248.     Wp->clear();
  249.     Wp->message(string("%d sites",N));
  250.     Wp->flush();
  251.  
  252.     for (i=0; i<N ; i++)
  253.     { point p(random(10,500),random(10,ymax));
  254.       DT.insert(p,i);
  255.       *Wp << p;
  256.      }
  257.  
  258.  
  259.     //DT.trace_voronoi_sites( draw_vor_site);
  260.  
  261.     DT.trace_voronoi_edges( draw_vor_seg,infi_pt);
  262.     Wp->flush();
  263.     wait(sec);
  264.  
  265.     Wp->clear();
  266.  
  267.     DT.trace_triang_edges( draw_triang_seg);
  268.     Wp->flush();
  269.     wait(sec);
  270.   }
  271.  
  272. }
  273.  
  274.  
  275. /*
  276. #include <LEDA/stream.h>
  277. */
  278.  
  279.  
  280. main(int argc, char** argv)
  281. {
  282.  
  283. /*
  284.  
  285. #define SCREEN_WIDTH  1152
  286. #define SCREEN_HEIGHT  900
  287.  
  288.   string_istream arguments(argc-1,argv+1);
  289.  
  290.   int   N=0;
  291.  
  292.   float f1=1; 
  293.   float f2=1;
  294.  
  295.   float w,h,xpos,ypos;
  296.  
  297.   int   position=0;
  298.  
  299.   arguments >> f1;
  300.   arguments >> f2;
  301.  
  302.   if (f1 == 0 && f2 == 0) 
  303.    { f1 = 0.75;
  304.      f2 = 0.95;
  305.     }
  306.   else 
  307.    if (f2 == 0) 
  308.      f2 = f1;
  309.    else
  310.      { arguments >> position;
  311.        arguments >> N;
  312.       }
  313.  
  314.  
  315.   w = SCREEN_WIDTH*f1;
  316.   h = SCREEN_HEIGHT*f2;
  317.  
  318.   switch(position) {
  319.  
  320.   case 0: xpos = SCREEN_WIDTH - w;    // upper right corner
  321.           ypos = 0;
  322.           break; 
  323.  
  324.   case 1: xpos = 0;                   // upper left corner
  325.           ypos = 0;
  326.           break; 
  327.  
  328.   case 2: xpos = 0;
  329.           ypos = SCREEN_HEIGHT - h;   // lower left corner
  330.           break; 
  331.  
  332.   case 3: xpos = SCREEN_WIDTH - w;    // lower right corner
  333.           ypos = SCREEN_HEIGHT - h;
  334.           break; 
  335. }
  336.  
  337.  
  338.   window W(w,h,xpos,ypos);
  339.  
  340. */
  341.  
  342.  
  343.   int N = (argc > 1) ? atoi(argv[1]) : 0;
  344.  
  345.   window W;
  346.  
  347.   W.set_flush(false);
  348.  
  349.   W.init(0,512,0);
  350.  
  351.   Wp = &W;
  352.  
  353.   ymax = int(W.ymax()-10);
  354.  
  355.   if (N==0) 
  356.      interactive(W);
  357.   else
  358.      demo(N,2);
  359.  
  360.  return 0;
  361. }
  362.